package zuo.algo.c05;

import zuo.algo.data.LinkedNode;
import zuo.algo.util.LinkedUtils;
import zuo.algo.util.SortUtils;

import java.util.LinkedList;

/**
 * 01:17-求链表是否是回文链表
 */
public class Palindrome {

    public static boolean check1(LinkedNode head) {
        LinkedList<LinkedNode> stack = new LinkedList<>();
        LinkedNode node = head;
        while (node != null) {
            stack.push(node);
            node = node.next;
        }
        node = head;
        while (node != null) {
            LinkedNode end = stack.pop();
            if (node.val != end.val) {
                return false;
            }
            node = node.next;
        }
        return true;
    }

    public static boolean check2(LinkedNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        LinkedNode fast = head;
        LinkedNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        LinkedNode mid = slow;
        LinkedNode head2 = mid.next;
        mid.next = null;
        LinkedNode node = head2;
        while (node != null && node.next != null) {
            LinkedNode next = node.next;
            node.next = next.next;
            next.next = head2;
            head2 = next;
        }
        LinkedNode node1 = head, node2 = head2;
        boolean res = true;
        while (node1 != null && node2 != null) {
            if (node1.val != node2.val) {
                res = false;
                break;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        node = head2;
        while (node != null && node.next != null) {
            LinkedNode next = node.next;
            node.next = next.next;
            next.next = head2;
            head2 = next;
        }
        mid.next = head2;
        return res;
    }

    public static void main(String[] args) {
        LinkedNode head = LinkedUtils.constructLinkedList(new int[]{1});
        boolean check1 = check1(head);
        boolean check2 = check2(head);
        if (check1 != check2) {
            throw new RuntimeException();
        }
        head = LinkedUtils.constructLinkedList(new int[]{1, 1});
        check1 = check1(head);
        check2 = check2(head);
        if (check1 != check2) {
            throw new RuntimeException();
        }
        head = LinkedUtils.constructLinkedList(new int[]{1, 2, 1});
        check1 = check1(head);
        check2 = check2(head);
        if (check1 != check2) {
            throw new RuntimeException();
        }
        head = LinkedUtils.constructLinkedList(new int[]{1, 2, 2, 1});
        check1 = check1(head);
        check2 = check2(head);
        if (check1 != check2) {
            throw new RuntimeException();
        }
        for (int i = 0; i < 1000000; i++) {
            int[] arr = SortUtils.getRandomArr(10000, 1000);
            head = LinkedUtils.constructLinkedList(arr);
            check1 = check1(head);
            check2 = check2(head);
            if (check1 != check2) {
                throw new RuntimeException();
            }
            System.out.println(i);
        }
    }
}
